//#define _CRT_SECURE_NO_WARNINGS 1
//
//#include<iostream>
//#include<string>
//#include<algorithm>
//using namespace std;
//
//
//string addStrings(string num1, string num2)
//{
//	string ret = "";
//	int carry = 0;
//	int i = num1.size() - 1;
//	int j = num2.size() - 1;
//
//	while (i >= 0 || j >= 0 || carry)
//	{
//		int sum = carry;
//		if (i >= 0)
//		{
//			sum += num1[i--] - '0';
//		}
//		if (j >= 0)
//		{
//			sum += num2[j--] - '0';
//		}
//		carry = sum / 10;
//		ret.push_back((sum % 10) + '0');
//	}
//	reverse(ret.begin(), ret.end());
//	return ret;
//}
//
//string fibonacci(int n)
//{
//	if (n == 0) return "0";
//	if (n == 1) return "1";
//
//	string a = "0", b = "1";
//	string ret = "";
//	for(int i = 2;i<=n;i++)
//	{
//		ret = addStrings(a, b);// 0 1 ->1 2->3 5 8 13 21 34
//		a = b;
//		b = ret;
//	}
//	return ret;
//}
//
//
//int main()
//{
//	int n;
//	cin >> n;
//	cout << fibonacci(n) << endl;
//
//	return 0;
//}